A solid model representing, by example, a part or a tool may be specified by combining subsolids or primitive volumes through set theoretic Boolean operations such as union, intersection, and difference of sets. The solid is represented by a set theoretic Boolean expression which can be efficiently stored within a computer memory in a binary tree representation or, more precisely, in a binary directed rooted acyclic graph.
FIG. 1 is an illustrative binary tree representation of a solid (1) which is composed of the union of two subsolids (2) and (3). Subsolid (3) is composed of the difference between the block primitive (4) and the cylindrical primitive (5). The form of such a tree is directly obtained by parsing the Boolean expression (2)+((4)-(5)). The root of the tree (solid 1) is associated with the solid defined by the Boolean expression. Internal nodes of the tree correspond to Boolean operations and are associated with subsolids. Leaves of the tree are associated with primitive volumes, which often are the intersection of relatively simple algebraic half-spaces, that is, regions of space where a simple polynomial function of three space coordinates has a non-positive value. For example, a ball of radius R centered at the origin is a half-space defined by the function x.sup.2 +y.sup.2 +z.sup.2 -R.sup.2 .ltoreq.0. An arbitrarily positioned and oriented primitive volume can be described in terms of a rigid motion transformation, a combination of a rotation with a translation, and of a congruent primitive volume defined in a convenient local coordinate system. Simple primitive volumes can be represented by their type, such as sphere, cylinder or cone, and by a relatively few intrinsic parameters such as radius, length and apex angle. Such a tree is known as a Constructive Solid Geometry representation, and will be abbreviated hereinafter as CSG.
The positions and dimensions, or intrinsic parameters of the primitive volumes may be expressed in terms of a few primary parameters which characterize a particular member in an entire family of solids represented by the CSG tree. The resulting parameterized CSG representation can therefore be conveniently used to model, for example, an assembly of parts whose dimensions vary within tolerance limits.
CSG objects are often constructed from primitives whose faces overlap. However, Boolean operations on solids having overlapping boundaries may create a non-regularized set. Therefore, CSG operators have conventionally been modified to always produce regularized solids. However, these modifications require additional processing.
Shading a CSG solid through boundary evaluation is generally an expensive data processing procedure. Efficient, direct approaches for shading CSG models through ray-casting are available for facetted models and for Boolean combinations of quadric half-spaces. However, ray-casting involves computing a large number of ray-surface intersections and becomes particularly inefficient when higher degree algebraic or parametric surfaces are involved.
In that surface evaluation is faster than ray-surface intersection, scan-conversion techniques with adaptive tesselation are often used for shading boundary models. A hardware depth-buffer (z-buffer) is used for automatically selecting the visible faces of the model. Because the faces of a CSG solid are not directly available, the depth-buffer visibility test must be combined with a trimming process that selects the portions of primitive faces that lie on the solid.
A software implementation of this selection has been combined with a hardware depth-test by one of the present inventors and is described in an article entitled "Depth buffering display techniques for constructive solid geometry", IEEE, Computer Graphics and Applications, vol. 6, no. 9, pp 29-39, Sep. 1986 by J. R. Rossignac and A. A. G. Requicha. This technique generally involves comparing a point P on a front-facing face of a primitive A to a depth stored in the z-buffer of the corresponding pixel. If P is in front of what is stored in the z-buffer, it is "classified", i.e. tested, against the CSG graph. Points on the boundary of the solid are rendered into the z-buffer. Points inside of or outside of the boundary of the solid are discarded. A point inside the solid is automatically rejected by the z-buffer visibility test. Therefore, performance is improved by avoiding a test of P against certain primitives in the graph by classifying P against an I-zone of A, the I-zone being an intersection of a subset of the nodes of the original CSG graph. If P lies inside the I-zone of A, it lies on the final solid or inside of the final solid.
Scan-conversion is a known technique that generates surface points that project onto individual screen pixels along the viewing direction. The depth of the three dimensional points, computed along the viewing direction away from the viewer, may be stored in the z-buffer memory associated with the corresponding pixel. A three dimensional point whose depth is stored in some pixel's z-buffer is classified against a primitive by scan-converting the boundary of the primitive and computing the parity of the number of layers of the primitive's surface that are behind the point being tested. This is accomplished by comparing against the value stored in the z-buffer the depth values of surface points that project onto the same pixel as the tested point. Each time the depth of the scanned point is larger than the stored point a binary parity flag associated with that pixel is inverted.
To classify a point against a CSG expression, it is not sufficient to classify the point only against all primitives. Point-primitive classification results must further be combined according to a Boolean expression. For some simple Boolean expression, such as an intersection, no storage is necessary because the result may be formulated as a conjunction of Boolean results. The classification algorithm may process the primitives in any order and then stop as soon as one of the results is FALSE. This would be the case when, for example, the point was out of a primitive in a Boolean intersection. If all the primitives are processed and no FALSE result is found, the point is inside the solid defined by the Boolean expression.
However, the evaluation of more complicated CSG expressions presents a problem in that a large amount of temporary storage may be required for intermediate binary results. Usually a stack mechanism is used for the temporary storage. The required stack depth may reach the depth of the CSG graph.
In that the amount of system memory per pixel is limited it is not practical to provide a stack of arbitrary depth at each pixel. Yet, it is desirable to perform classification operations in parallel for all pixels, so as to minimize the number of required primitive scan-conversions.
A technique described by J. Goldfeather et al. "Near Real-Time CSG Rendering using Tree Normalization and Geometric Pruning" in IEEE CG&A, vol. 9, no. 3, pp. 20-28, June 1989, circumvents the memory limitation by converting the CSG expression into a significantly larger sum-of-product form in which primitive instances may be duplicated many times, thereby appearing in several products. Techniques for eliminating redundant (empty) products are also discussed.
In this technique primitive faces are first trimmed against the appropriate products using repeated primitive scan-conversions. The resulting trimmed faces are then merged using a final depth buffer for selecting the front-most faces among all the products. A z-buffer is used for both visible surface selection and for discarding faces interior to the solid.
It is noted however that products may interfere and, therefore, a front face of a product may not lie on the solid.
As a result, there is a need, in regard to the projective approach to CSG processing, for an efficient and accurate method for determining the visible front-faces of a product. In that depth-buffer comparisons are performed within the limited resolution of the z-buffer, there is a further need to correctly handle situations where faces of several primitives overlap or where a ray of a pixel intersects two adjacent faces very close to their common edge.
For both of these cases, due to scan-conversion round-off errors, computed depth values may not be accurate. However, despite these inherent inaccuracies, there remains the requirement to generate a displayable image that corresponds to a regularized version of the CSG expression. A solid is considered to be regularized when it is equal to the topological closure of its interior with respect to three-dimensional Euclidean space. Regularized solids therefore have, by definition, no dangling edges or faces. Thus, faces or edges that lie on several primitives, but are not bounding any three-dimensional volume in the final result, should not be displayed.
The following U.S. patents teach various aspects of image display and/or CSG rendering. In U.S. Pat. No. 4,609,917, Sep. 2, 1986, T. Y. Shen discloses a variation of a commonly used graphics architecture employing z-buffers. In U.S. Pat. No. 4,625,289, Nov. 25, 1986, A. P. Rockwood discloses a method of surface display in which points on the surface are generated by sampling a function describing the surface. A z-buffer is employed to find the nearest sampled point to the viewer for every pixel covered by the sampling. In U.S. Pat. No. 4,736,306, Apr. 5, 1988, Christensen et al., issued Apr. 5, 1988 disclose a boundary-to-CSG conversion technique. In U.S. Pat. No. 4,737,921, Apr. 12, 1988, Goldwasser, et al. disclose a multiprocessor system for displaying pixel data. Specifically, a hardware architecture is proposed for merging images (intensity and depth) that are computed in parallel by several processors, with a possibility for moving individual images in realtime shadowing processors are also provided in this system. In U.S. Pat. No. 4,821,214, Apr. 11, 1989, T. W. Sederberg discloses a technique for obtaining a free-form deformation of a model through the use of a trivariate vector rational polynomial. The method is said to be applicable to CSG solid modelling systems. In U.S. Pat. No. 4,825,391, Apr. 25, 1989, D. M. Merz discloses a visible surface architecture in which span comparisons are used instead of depth memory. In U.S. Pat. No. 4,855,938, Aug. 8, 1989, J. Lopez et al. disclose a method of displaying visible lines of polygons. A z-buffer is initialized with special z values for the polygon edges. The polygon is rasterized into the z-buffer and only those pixels which still have the special z-values are appropriately colored. In U.S. Pat. No. 4,907,174, Mar. 6, 1990, C. Priem discloses the use of a range of z-depths in a portion of a z-buffer to identify which graphics display window a z-buffer is dedicated to.
Finally, in U.S. Pat. No. 4,858,149, Aug. 15, 1989, P. Quarendon discloses solid modeling to render CSG objects. A universe is decomposed recursively into smaller and smaller cubes until the cube does not intersect any primitive's boundary or until the cube is smaller than a current resolution. Although this patent is relevant to the solution of the problem solved by the present invention, the approach is less efficient and does not employ hardware depth-buffers.
Researchers have implemented a hardware algorithm for trimming primitive faces by comparing them to all front and back faces of all primitives in a product. The comparisons are performed independently at each pixel and involve depth tests, masks, counters, and logical bit operations performed at each pixel. This technique uses but two additional buffers. The algorithm has been implemented on a Pixel-Power graphic system having one processor with local memory at each pixel. This approach is described in the already mentioned journal article by J. Goldfeather et al. "Near Real-Time CSG Rendering using Tree Normalization and Geometric Pruning" in IEEE CG&A, vol. 9, no. 3, pp. 20-28, June 1989.
Other researchers, including certain of the present inventors, have developed a more efficient technique for processing products. This technique is referred to as a "trickle" algorithm and requires, in general, fewer primitive scan-conversion and buffer-merging operations than the technique of Goldfeather et al. As a result, this technique is believed to be better suited for implementation on emerging graphic workstations. The trickle algorithm is described in a Research Report entitled "Z-buffer Rendering from CSG: the Trickle Algorithm", RC 15182 (#67629) November 1989, IBM Research Division, by D. A. Epstein, F. W. Jansen and J. R. Rossignac.
Both the technique described by Goldfeather et. al. and the technique described by Epstein et al. process non-convex primitives by producing and trimming the successive layers of a primitive's hidden faces.
An important feature of the trickle algorithm is that it processes the primitive faces of a product in a front-to-back (away from the viewer) order independently at each pixel. This ordering permits the technique to stop the processing of a given product as soon as a visible point, or the background, has been reached at each pixel covered by the product's projection. Furthermore, while moving "deeper" (away from the viewer) from one primitive-face layer to another, the trickle algorithm advantageously skips primitive-face layers that clearly cannot lie on the product because they are out of at least one primitive in the product.
The trickle algorithm employs three depth and intensity buffers. These are the standard depth and intensity buffers used for visible surface selection, plus an additional depth-interval buffer composed to two depth buffers and two intensity buffers. It should be noted that the trickle algorithm may be configured to run in four passes, once for each quadrant of the screen. Splitting the screen into four quadrants provides sufficient buffers for the trickle algorithm, even with the standard configuration of one depth and two intensity buffers commonly available on graphic workstations.
It is thus an object of the invention to provide improvements and enhancements to the trickle algorithm to even further improve the processing of CSG-represented solids.
It is a further object of the invention to provide an efficient and accurate shadowing technique for CSG representations of solid objects.
Another object of the invention is to provide for an efficient method of determining visible front-faces of a product and for correctly handling situations where faces of several primitives overlap or where the ray of a pixel intersects two adjacent faces at a point near to a common edge, the method employing a small tolerance value to remove the effects of round-off error during scan-conversion.
A further object of the invention is to provide a method to terminate the scan conversion of a product's primitives at a time when further scan-conversions are determined to be unnecessary.
One still further object of the invention is to provide a method of improving the accuracy of rendering (i.e. scan conversion) of faces, the method employing a determination of an accurate depth value of a surface at the center of a pixel upon which the vertex subset of the surface projects.